Главная /
Рефераты / МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО (ЦЕЛОЧИСЛЕННОГО) ПРОГРАММИРОВАНИЯ
МЕТОДЫ РЕШЕНИЯ ЗАДАЧ ДИСКРЕТНОГО (ЦЕЛОЧИСЛЕННОГО) ПРОГРАММИРОВАНИЯ
Дискретное программирование используется для решения задач с детерминированной целевой функцией при ограничениях на значения переменных.
Примерами таких задач являются: определение очередности выполнения работ, назначение ресурсов по объектам использования, выбор маршрута на сети "задача о коммивояжере".
Основной особенностью является то, что все или некоторые переменные должны принимать только целочисленные (дискретные) значения. Обычно это бывает при описании неделимых объектов (людей, машин и т.п.) или при наложении жестких ограничений типа равенств.
При решении задач возникают сложности с выбором специальных дополнительных ограничений для отсечения области решений с нецелочисленными переменными, которые часто приходится выбирать по эвристическим правилам.
Различают два класса методов решения задач дискретного программирования: методы отсечения и комбинаторные методы.
Методы отсечений используются при решении линейных целочисленных задач без булевых переменных. Их идея заключается в ослаблении ограничений (за счет отказа от требований целочисленности) и решении обычной задачи линейного программирования. Затем, если полученное оптимальное решение не удовлетворяет требованию целочисленности, вводят специальные дополнительные требования, тем самым отсекая некоторую область возможных решений, и вновь решают задачу линейного программирования с проверкой результатов на целочисленность переменных.
Процесс повторяется до выполнения требований по целочисленности. Для решения целочисленных задач используется алгоритм Гомори и алгоритм Дальтона и Ллевелина (см. [6.57]).
Комбинаторные методы используются для решения нелинейных задач с булевыми переменными. Для таких задач используется так называемый аддитивный алгоритм, вычислительные операции в котором осуществляют вычитанием. Идея аддитивного алгоритма заключается в переборе 2N возможных решений (где N — число булевых переменных) и выбор лучшего из них (см. [6.45; 6.55]).
Похожие рефераты:
